package com.wyw.learning.offer;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 第一个只出现一次的字符
 *  在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/20 15:05
 */
public class Offer050 {

    public static void main(String[] args) {
        String s = "abcdefgasbeca";
        System.out.println(firstUniqChar(s));
    }

    // 字典查找
//    public static char firstUniqChar(String s) {
//        if (s.equals("")) return ' ';
//        //创建‘a'-'z'的字典
//        int[] target = new int[26];
//        //第一次遍历，将字符统计到字典数组
//        for (int i = 0; i < s.length(); i++) {
//            target[s.charAt(i) - 'a']++;
//        }
//        //第二次遍历，从字典数组获取次数
//        for (int i = 0; i < s.length(); i++) {
//            if (target[s.charAt(i) - 'a'] == 1) return s.charAt(i);
//        }
//
//        return ' ';
//    }


    // 哈希表
//    public static char firstUniqChar(String s) {
//        HashMap<Character, Integer> map = new HashMap();
//        for(int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            map.put(c, map.getOrDefault(c, 0) + 1);
//        }
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if(map.get(c) == 1) {
//                return c;
//            }
//        }
//        return ' ';
//    }

    // 上述哈希改造
//    public static char firstUniqChar(String s) {
//        Map<Character, Integer> position = new HashMap<>();
//        int n = s.length();
//        for (int i = 0; i < n; ++i) {
//            char ch = s.charAt(i);
//            if (position.containsKey(ch)) {
//                position.put(ch, -1);
//            } else {
//                position.put(ch, i);
//            }
//        }
//        int first = n;
//        for (Map.Entry<Character, Integer> entry : position.entrySet()) {
//            int pos = entry.getValue();
//            if (pos != -1 && pos < first) {
//                first = pos;
//            }
//        }
//        return first == n ? ' ' : s.charAt(first);
//    }


    // 队列
    public static char firstUniqChar(String s) {
        Map<Character, Integer> position = new HashMap<>();
        Queue<Pair> queue = new LinkedList<>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) {
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            } else {
                position.put(ch, -1);
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? ' ' : queue.poll().ch;
    }




}

class Pair {
    char ch;
    int pos;

    Pair(char ch, int pos) {
        this.ch = ch;
        this.pos = pos;
    }
}
